package com.剑指offer.第二章;

public class 二维子矩阵的数字之和 {

    private static int[][] sums;

    public static void initSum(int[][] matrix) {
        sums = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            int rownum = 0;
            for (int j = 0; j < matrix[0].length; j++) {
                rownum += matrix[i][j];
                sums[i + 1][j + 1] = sums[i][j + 1] + rownum;
            }
        }
    }

    /**
     * 如果输入的矩阵的行数和列数分别是m和n，那么辅助数组sums的行数和列数分别为m+1,n+1
     * 这样只是为了简化代码逻辑。如果用公式sums[row2 ][col2 ] - sums[row1-1][col2 ] - sums[row2][col1-1] + sums[row1-1][col1-1]
     * 左上角有可能是(0,0)，因此r1-1，c1-1可能是负数
     *
     * @param row1
     * @param col1
     * @param row2
     * @param col2
     * @return
     */
    public static int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }

    public static void main(String[] args) {

    }

}
